//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/submissions/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int INF = 0x3f3f3f; // 无穷大的常量，表示一个很大的数
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF)); // f[i][j] ：表示第j次交易时处于买入状态的最大利润
        auto g = f; // g[i][j] ：表示第j次交易时处于卖出状态的最大利润
        f[0][0] = -prices[0]; // 第一次交易买入
        g[0][0] = 0; // 第一次交易卖出
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                // 计算第i次交易买入的最大利润
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                
                // 计算第i次交易卖出的最大利润
                g[i][j] = g[i - 1][j];
                if(j > 0)
                {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        // 返回动态规划表中最后一行的买入状态的最大利润
        return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));
    }
};